/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhong
 *
 */
public class IPtoCIDR {
	public List<String> ipToCIDR(String ip, int range) {
		List<String> reStrings = new ArrayList<>();
		StringBuilder currentIP = getTotalBinaryRep(ip);

		while (range > 0) {
			int j = currentIP.length() - 1;
			while (j >= 0 && currentIP.charAt(j) == '0') {
				j--;
			}
			if (j == -1) {// 全部都是1,即255.255.255
				range--;
				StringBuilder sBuilder = new StringBuilder(currentIP);
				sBuilder.append('/');
				sBuilder.append(32);
				reStrings.add(sBuilder.toString());
				continue;
			} else {// 找到了第一个1，则后面的位数是
				int leftCount = currentIP.length() - 1 - j;// 左边0的个数
				int size = 1 << leftCount;
				while (range < size) {
					size = size >> 1;
					leftCount--;
					j++;
				}
				// 掩码的右侧为0
				StringBuilder zeroEnd = new StringBuilder(currentIP);
				for (int i = j + 1; i < 32; i++) {
					zeroEnd.setCharAt(i, '0');
				}
				System.out.println("Yanma: " + zeroEnd);
				// 计算next
				StringBuilder next = new StringBuilder(currentIP);
				while (j >= 0 && next.charAt(j) != '0') {
					j--;
				}
				// 设置为1，右侧为0
				next.setCharAt(j, '1');
				for (int i = j + 1; i < 32; i++) {
					next.setCharAt(i, '0');
				}
				currentIP = next;
				reStrings.add(binarTotal2Str(zeroEnd) + "/" + (32 - leftCount));
				range -= size;
			}
		}
		return reStrings;
	}

	/**
	 * 十进制带.的ip表示转成二进制32位01表示
	 * 
	 * @param ip
	 * @return
	 */
	private StringBuilder getTotalBinaryRep(String ip) {
		StringBuilder res = new StringBuilder();
		String[] sub = ip.split("\\.");
		for (int i = 0; i < 4; i++) {
			String string = Integer.toBinaryString(Integer.parseInt(sub[i]));
			StringBuilder sBuilder = new StringBuilder();
			for (int j = string.length(); j < 8; j++) {// 每个section有8位
				sBuilder.append('0');
			}
			sBuilder.append(string);
			res.append(sBuilder);
		}
		return res;
	}

	/**
	 * 
	 * @param sBuilder
	 *            全部二进制表示，即32为01表示，没有.号，.section
	 * @return 有都好分割的ip的十进制表示
	 */
	private String binarTotal2Str(StringBuilder sBuilder) {
		StringBuilder reStringBuilder = new StringBuilder();
		for (int i = 0; i < 4; i++) {
			String tmp = sBuilder.substring(i * 8, (i + 1) * 8);
			reStringBuilder.append(Integer.parseInt(tmp, 2));
			if (i != 3) {
				reStringBuilder.append('.');
			}
		}
		return reStringBuilder.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String ip = "255.0.0.7";

		int n = 10;
		System.out.println(new IPtoCIDR().ipToCIDR(ip, n));
	}

}
